'''
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

 


Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

 


The largest rectangle is shown in the shaded area, which has area = 10 unit.

 

Example:

Input: [2,1,5,6,2,3]
Output: 10
'''

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        '''
        20201009--李运辰
        不太熟
        '''
        #stack表示长度
        stack, ans, heights = [-1], 0, heights+[0]

        for i in range(len(heights)):
            #print(i)
            #print(stack)
            #print(ans)
            #print('-------')
            #出现非升序或者降序的元素
            while stack[-1] != -1 and heights[stack[-1]] >= heights[i]:
                ans = max(ans, heights[stack.pop()]*(i-1-stack[-1]))
            stack.append(i)
        return ans